package com.kehao.leetcode.order;

import org.junit.Test;

import java.util.Stack;

public class LeetcodeSolution907 {
    public int sumSubarrayMins(int[] arr) {
        int mod = 1_000_000_007;
        int[] left = new int[arr.length];
        int[] right = new int[arr.length];
        Stack<Integer> stack = new Stack<>();
        long sum = 0;
        for (int i = 0; i < arr.length; i++) {
            while ((!stack.isEmpty())&&arr[stack.peek()]>arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                left[i] = -1;
            }else {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = arr.length-1; i >=0 ; i--) {
            while ((!stack.isEmpty())&&arr[stack.peek()]>=arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = arr.length;
            }else {
                right[i] = stack.peek();
            }
            stack.push(i);
        }
        for (int i = 0; i < arr.length; i++) {
            sum+= (i-left[i])*(long)(right[i]-i)*arr[i];
            sum = sum%mod;
        }
        return (int) sum%mod;
    }

    @Test
    public void test(){
        int[] arr = {3,1,2,4};
        int res = sumSubarrayMins(arr);
        System.out.println(res);
    }
}
